// https://leetcode.cn/problems/validate-binary-search-tree/description/

package binarytree

func IsValidBST(root *TreeNode) bool {
	return isValidBSTHelper(root, nil, nil)
}

// 思路：
// 1. 二叉搜索树的定义：
//   - 左子树的所有节点值小于根节点值
//   - 右子树的所有节点值大于根节点值
//
// 2. 递归检查每个节点，维护一个范围 [min, max]，
//   - 对于每个节点，检查其值是否在这个范围内
//   - 如果当前节点的值小于等于 min 或大于等于 max，则不是二叉搜索树
//     3. 对于左子树，更新 max 为当前节点值；
//     对于右子树，更新 min 为当前节点值
//     4. 递归检查左子树和右子树，直到所有节点都满足二叉搜索树的条件
//     5. 如果所有节点都满足条件，则返回 true，否则返回 false
//     6. 边界情况：
//   - 如果节点为 nil，则返回 true（空树是二叉搜索树）
//     7. 注意：
//   - 在递归过程中，使用指针来传递 min 和 max 的值，以避免在每次递归时都创建新的变量
//     8. 时间复杂度：O(n)，其中 n 是树中的节点数，因为每个节点都被访问一次
//     9. 空间复杂度：O(h)，其中 h 是树的高度，递归调用栈的空间复杂度
//
// -----------
// 这种自上而下携带 min 和 max 的方式，比较直观，属于用深度而不是高度的方法来遍历
func isValidBSTHelper(node *TreeNode, min *int, max *int) bool {
	if node == nil {
		return true
	}
	if (min != nil && node.Val <= *min) || (max != nil && node.Val >= *max) {
		return false
	}
	return isValidBSTHelper(node.Left, min, &node.Val) && isValidBSTHelper(node.Right, &node.Val, max)
}

// 这个是我自己写的，思路上最大的区别就是自下而上，依赖子树告知最大值和最小值
// 这种方式显得麻烦了一点!!!
func IsValidBSTSelf(root *TreeNode) bool {
	// 判断逻辑倒是很简单
	// 从根节点开始:
	// + 看一下左子树是不是BST(isLeftBST)，是的话最大值节点是谁 max；
	// + 看一下右子树是不是BST(isRightBST)，是的话最小值节点是谁 min；
	// 得到了如上信息，做如下判断
	// + isLeftBST 和 isRightBST 只要有一个不是BST，则必然不是BST!!!
	// + leftMax.Val < node.Val < rightMin.Val 的话，这就是一颗 BST !!!
	// 子问题已经抽象出来了，下边是临界值的判断：
	// 1. 只要左右子树都是nil，则必然是BST
	// 2. 左子树为nil的话，我们只需要比较 node.Val 和 rightMin.Val 即可了；同理右子树为nil的情况。
	// 3. 左右子树都不是nil，常规判断。
	// 所以我们抽象的函数还是要同时返回三个参数：
	// 1. 是否是BST
	// 2. min
	// 3. max (min 和 max 有可能一样大)
	var check func(node *TreeNode) (bool, *TreeNode, *TreeNode)
	check = func(node *TreeNode) (bool, *TreeNode, *TreeNode) {
		if node.Left == nil && node.Right == nil {
			return true, node, node
		}

		if node.Left != nil && node.Right != nil {
			leftBST, leftMin, leftMax := check(node.Left)
			rightBST, rightMin, rightMax := check(node.Right)
			if leftBST && rightBST && leftMax.Val < node.Val && node.Val < rightMin.Val {
				return true, leftMin, rightMax
			}
		}

		if node.Left == nil && node.Right != nil {
			rightBST, rightMin, rightMax := check(node.Right)
			if rightBST && node.Val < rightMin.Val {
				return true, node, rightMax
			}
		}

		if node.Left != nil && node.Right == nil {
			leftBST, leftMin, leftMax := check(node.Left)
			if leftBST && leftMax.Val < node.Val {
				return true, leftMin, node
			}
		}

		return false, nil, nil
	}

	isBST, _, _ := check(root)
	return isBST
}

// 还有一个更简单的思路，就是中序遍历
// 中序遍历二叉搜索树的结果是一个有序数组就说明是一个二叉搜索树!!!!
